/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class MaxChunksToMakeSorted {
	public int maxChunksToSorted(int[] arr) {
		int n = arr.length;
		boolean[] visited = new boolean[n];
		int res = 0;
		for (int i = 0; i < n; i++) {
			if (visited[i])
				continue;
			res++;
			DFS(i, visited, arr);

		}
		return res;
	}

	private void DFS(int i, boolean[] visited, int[] arr) {
		if (visited[i])
			return;
		visited[i] = true;
		int pos = i;
		int min = Math.min(pos, arr[pos]);
		int max = Math.max(pos, arr[pos]);
		for (int j = min; j <= max; j++) {
			DFS(j, visited, arr);
		}
		pos = arr[pos];
		visited[pos] = true;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] arr = { 1, 0, 2, 3, 4 };// 1,0,2,3,4//4, 3, 2, 1, 0
		System.out.println(new MaxChunksToMakeSorted().maxChunksToSorted(arr));
	}

}
